package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class _234_PalindromeLinkedList {
    public static void main(String[] args) {
        Solution solution = new _234_PalindromeLinkedList().new Solution();
        ListNode a4 = new _234_PalindromeLinkedList().new ListNode(1, null);
        ListNode a3 = new _234_PalindromeLinkedList().new ListNode(2, a4);
        ListNode a2 = new _234_PalindromeLinkedList().new ListNode(1, a3);
        ListNode a1 = new _234_PalindromeLinkedList().new ListNode(1, a2);
        boolean b = solution.isPalindrome(a1);
        System.out.println(b);
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 利用 List
    class Solution1 {
        public boolean isPalindrome(ListNode head) {
            List<Integer> list = new ArrayList<>();
            while (head != null) {
                list.add(head.val);
                head = head.next;
            }
            int n = list.size();
            for (int i = 0, j = n - 1; j > i; i++, j--) {
                if (!list.get(i).equals(list.get(j))) {
                    return false;
                }
            }
            return true;
        }
    }

    // 整个链表进行翻转
    class Solution2 {

        private ListNode reverse(ListNode head) {
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null) {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            return prev;
        }

        public boolean isPalindrome(ListNode head) {
            ListNode dummy = new ListNode(-1, null);
            ListNode dummyHead = dummy;
            ListNode copyHead = head;
            while (copyHead != null) {
                dummy.next = new ListNode(copyHead.val, null);
                dummy = dummy.next;
                copyHead = copyHead.next;
            }
            ListNode reverseList = reverse(dummyHead);
            while (head != null) {
                if (head.val != reverseList.val) {
                    return false;
                }
                head = head.next;
                reverseList = reverseList.next;
            }
            return true;
        }
    }

    // 后 n / 2 个链表进行翻转
    class Solution {

        private ListNode half(ListNode head) {
            ListNode fast = head, slow = head;
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }

        private ListNode reverseNode(ListNode head) {
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null) {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            return prev;
        }

        public boolean isPalindrome(ListNode head) {
            if (head == null) {
                return true;
            }
            ListNode endOfFirstHalf = half(head);
            ListNode p2 = reverseNode(endOfFirstHalf.next);

            while (p2 != null) {
                if (head.val != p2.val) {
                    return false;
                }
                head = head.next;
                p2 = p2.next;
            }

            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}